package com.zjw.yyyy2021.mmdd0925;

/**
 * <p>最长子序列</p>
 *
 * @author 郑大仙丶
 * @version V1.0.0
 * @date 2021/9/25 22:40
 */
public class MMdd0925 {

    public int longestCommonSubSequence(String text1, String text2) {
        if(text1 == null || text2 == null) return 0;
        //1. 获取长度
        int m = text1.length();
        int n = text2.length();
        //2. 声明二位数组
        int[][] df = new int[m+1][n+1];
        //3. 遍历text1
        for (int i = 1; i < m + 1; i++) {
            char d = text1.charAt(i - 1);
            for (int j = 1; j < n + 1; j++) {
                char f = text2.charAt(j - 1);
                if(d == f){
                    df[i][j] = df[i - 1][j - 1] + 1;
                }else{
                    df[i][j] = Math.max(df[i - 1][j],df[i][j - 1]);
                }
            }
        }
        //4. 返回最后一位
        return df[m][n];
    }


    public static void main(String[] args) {
        String text1 = "people";
        String text2 = "poaple";
        System.out.println(new MMdd0925().longestCommonSubSequence(text1, text2));
    }


}
